package com.ztom.v2;

/**
 * @author ZhangTao
 */
public class Code97MajorityElement {

    public int majorityElement(int[] nums) {
        // 计数
        int count = 1;
        int maj = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == maj) {
                count++;
            } else {
                count--;
                // 取下个位置
                if (count == 0) {
                    maj = nums[i + 1];
                }
            }
        }
        return maj;
    }

    public int majorityElement1(int[] nums) {
        // 排序
        qs(nums, 0, nums.length - 1);
        return nums[nums.length / 2];
    }

    public void qs(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        swap(nums, end, (int) (start + Math.random() * (end - start + 1)));
        int[] mid = partition(nums, start, end);
        qs(nums, start, mid[0] - 1);
        qs(nums, mid[1] + 1, end);
    }

    public int[] partition(int[] nums, int start, int end) {
        if (start == end) {
            return new int[]{start, end};
        }
        int l = start - 1;
        int r = end;
        int num = nums[end];
        int index = start;
        while (index < r) {
            if (nums[index] < num) {
                swap(nums, index++, ++l);
            } else if (nums[index] > num) {
                swap(nums, index, --r);
            } else {
                index++;
            }
        }
        swap(nums, r, end);
        return new int[]{++l, r};
    }

    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
